package interviewQuestions;

import java.util.Scanner;

/**
 * 最小字典序排序字符串
 * 给定长度为N，且仅由大写字母组成的字符串S，要求通过S构造相同长度的字符串T。
 *
 * 一开始，T是一个空串。随后进行N次以下任一操作：
 *
 * 将S最左侧的字符取出，添加到T的右侧；
 * 将S最右侧的字符取出，添加到T的右侧。
 * 输出可以产生的具有最小字典序的字符串T。
 *
 * 其中N <= 2000。
 *
 * 示例1
 * 输入
 * ACDBCB
 *
 * 输出
 * ABCBCD
 *
 * */
public class MinDicSortofString {

    public static int fun(char[] chars,int first,int last){
        if(first >= last){
            return 0;
        }

        if(chars[first] > chars[last]){
            return 0;
        }else if(chars[first] < chars[last]){
            return 1;
        }else{
            return fun(chars,first+1,last-1);
        }
    }


    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String str = input.nextLine();
        char[] chars = str.toCharArray();
        char[] t = new char[str.length()];
        if(str.isEmpty() || str == null){
            return;
        }

        int first=0,last=str.length()-1;
        int i = 0;
        while(first <= last){
            if(chars[first] < chars[last]){
                t[i++] = chars[first];
                first++;
            }else if(chars[first] > chars[last]){
                t[i++] = chars[last];
                last--;
            }else{
                if(fun(chars,first+1,last-1) == 1){
                    t[i++] = chars[first];
                    first++;
                }else{
                    t[i++] = chars[last];
                    last--;
                }

            }
        }
        for (char c : t){
            System.out.print(c);
        }

    }

}
